package cm.unit3.theme3;

import cm.commom.ListNode;

public class DeleteDuplication {

    // 一个简单的链表删除题
    public ListNode deleteDuplication(ListNode pHead){
        if (pHead==null || pHead.next==null){
            return pHead;
        }

        // ------- 下面处理的链表至少有两个节点 -------------
        ListNode nullHead = new ListNode(Integer.MIN_VALUE);
        nullHead.next = pHead;

        ListNode curPtr = nullHead;

        while (curPtr.next!=null){
            if (is2Delete(curPtr.next)){
                deleteNode(curPtr,curPtr.next);
            }else{
                curPtr = curPtr.next;
            }
        }
        return nullHead.next;
    }

    public static boolean is2Delete(ListNode node){
        return node.next != null && node.val == node.next.val;
    }

    public static void deleteNode(ListNode prePtr,ListNode node){
        while (node.next!=null && node.val==node.next.val){
            node = node.next;
        }
        prePtr.next = node.next;
    }

    public static ListNode buildList(int []nodes){
        if (nodes==null){
            return null;
        }
        if (nodes.length==1){
            return new ListNode(nodes[0]);
        }

        ListNode head = new ListNode( nodes[nodes.length-1] );
        ListNode listNode;

        for (int i = nodes.length-2; i >= 0 ; i--) {
            listNode = new ListNode(nodes[i]);
            listNode.next = head;
            head = listNode;
        }
        return head;
    }

    public static String getListString(ListNode head){
        ListNode node = head;
        String result = "";
        while (node.next!=null){
            result += node.val + " ";
            node = node.next;
        }
        result += node.val;
        return result;
    }

    public static void main(String[] args) {
        int nodes[] = {1,2,3,3,3,3,4,4,5};
        ListNode head = buildList(nodes);
        System.out.println(getListString(head));


        DeleteDuplication delDup = new DeleteDuplication();
        ListNode newHead = delDup.deleteDuplication(head);
        System.out.println(getListString(head));

    }
}
